# coding=utf-8
# Date: 2021/8/30 14:19
from typing import List
import random
from bisect import bisect_left


# 执行用时：180 ms, 在所有 Python3 提交中击败了83.19%的用户
# 内存消耗：19.4 MB, 在所有 Python3 提交中击败了60.00%的用户
class Solution:

    def __init__(self, w: List[int]):
        self.s = w.copy()
        for i in range(1, len(w)):
            self.s[i] += self.s[i - 1]
        self.t = self.s[len(self.s) - 1]


    def pickIndex(self) -> int:
        x = random.randint(1, self.t)
        return bisect_left(self.s, x)


if __name__ == "__main__":
    t = Solution([1, 2, 3])
    for i in range(100):
        print(t.pickIndex())
